---
title: 索引底层的数据结构
description: 为什么常用B+树作为索引的数据结构？Hash索引的底层原理？
---
## 如何评价索引的数据结构设计好坏
数据库服务器的存储介质有两种，分为硬盘和内存。内存属于临时存储，容量有限，而且当发生意外时（比如断电或者发生故障重启）会发生数据丢失；硬盘相当于永久介质，这也是为什么我们需要把数据保存在硬盘上。

在硬盘上进行查询时，也就产生了硬盘的 I/O 操作。相比于内存的存取来说，硬盘的 I/O 存取消耗的时间要高很多。我们通过索引查找某行数据的时候，需要计算产生的磁盘 I/O 次数，当磁盘 I/O 次数越多，所消耗的时间也就越大。如果我们能让索引的数据结构尽量减少磁盘的 I/O 操作，所消耗的时间也就越短。

## 二叉树
二分查找法是一种高效的数据检索方法，时间复杂度为 O(log2n)。但二叉树并不适合作为索引的数据结构。


先来看下最基础的二叉搜索树（Binary Search Tree），搜索某个节点和插入节点的规则一样，我们假设搜索插入的数值为 key:

1. 如果 key 大于根节点，则在右子树中进行查找；
2. 如果 key 小于根节点，则在左子树中进行查找；
3. 如果 key 等于根节点，也就是找到了这个节点，返回根节点即可。

举个例子，我们对数列（33，22，89，5，23，77，91）创造出来的二分查找树如下图所示：

![12](https://img.wkq.pub/spring/19dedac56fdba8e7119352e84eb7af69.webp)

但是存在特殊的情况，就是有时候二叉树的深度非常大。比如我们给出的数据顺序是 (5,22,23,34,77,89,91),创造出来的二分搜素树如下图所示：

![](https://img.wkq.pub/spring/aedbdcc05f4a05177f1b599a59581133.webp)

第一个数的深度是 3 ，也就是说最多只需 3 次比较，就可以找到节点，而第二个树的深度是 7 ，最少需要 7 次比较才能找到节点。

第二棵树也属于二分查找树，但是性能上已经退化成了一条链表，查找数据的时间复杂度变成了 O(n) 。为了解决，人们提出了平衡二叉搜素树（AVL树）。它在二分搜索树的基础上增加了约束，每个节点的左子树和右子树的高度差不能超过 1，也就是说节点的左子树和右子树仍为平衡二叉树。

常见的平衡二叉树有很多种，包括了平衡二叉搜索树、红黑树、树堆、伸展树。平衡二叉树是最早提出来的自平衡二叉搜素树。

数据查询的时间主要依赖于磁盘的 I/O 的次数，如果我们采用二叉树的形式，，及时通过平衡二叉搜索树进行了改进，树的深度也是 O(log2n),  当 n 比较大时，深度也是比较高的，比如下图中的情况：

![](https://img.wkq.pub/spring/78154f20220d6fedb95ebbac61bd5cea.webp)

每访问一次节点就需要进行一次磁盘 I/O 操作，对于上面的树来说，我们需要进行 5 次磁盘 I/O 操作。虽然平衡二叉树的比较的效率高，但是树的深度也同样高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。

## B树

如果用二叉树作为索引的实现结构，会让树变得很高，增加磁盘的 I/O  次数，影响数据查询的时间。因此一个节点就不能只有两个子节点，而应该允许有 M 个子节点(M>2)。



B 树的出现就是为了解决这个问题，B 树的英文是 Balance Tree，也就是平衡的多路搜索树，他的高度远小于平衡二叉树的高度。在文件系统和数据库系统中的索引结构经常采用 B 树来实现。



B树的结构如下图所示：

![](https://img.wkq.pub/spring/18031c20f9a4be3e858743ed99f3c144.webp)

B 树的每一个节点做多可以包括 M 个子节点，M 称为 B 树的阶。

每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包含了 x 个关键字，那么指针数就是 x + 1。对于一个 100 阶的 B 树来说，如果有 3 层的话



## Hash索引的底层原理是什么？
Hash 本身是一个函数
